package Offer.offer;

import domain.ComplexListNode;

/**
 * 复杂链表的复制
 * Created by 雷文康 on 2018/1/1.
 */
public class Test26复杂链表的复制 {

    public static ComplexListNode cloneComplexNodes(ComplexListNode head){
        if (head == null){
            return null;
        }
        cloneNode(head);
        setSibling(head);
        return getNewList(head);
    }

    public static void cloneNode(ComplexListNode head){
        ComplexListNode p = head;
        while (p != null){
            ComplexListNode clone = new ComplexListNode(p.val);
            clone.next = p.next;
            p.next = clone;
            p = clone.next;
        }
    }

    public static void setSibling(ComplexListNode head){
        ComplexListNode p = head;
        while (p != null){
            ComplexListNode pclone = p.next;
            if (p.sibling != null){
                pclone.sibling = p.sibling.next;
            }
            p = pclone.next;
        }
    }

    public static ComplexListNode getNewList(ComplexListNode head){

        ComplexListNode newHead = head.next;
        ComplexListNode p = head;
        while (p != null){
            ComplexListNode pclone = p.next;
            p.next = pclone.next;
            if (p.next != null){
                pclone.next = p.next.next;
                p = p.next;
            }
        }
        return newHead;
    }

}
